package com.arithmeticEveryDay.luoguOJ;

import java.util.Scanner;

/*

先假设出dp数组
dp[i][j]表示从索引0~i的物品中选择，剩余j块钱可以买的价格与重要度乘积最大的方案

            0   10      20      30      40      50      60      70      80      90      100
0           0   0       0       0       0       0       0       0       0       0       0
1(80,2,0)   0   0       0       0       0       0       0       0       160     160     160
2(40,5,1)   0   0       0       0       0       0       0       0       160     160     160
3(30,5,1)   0   0       0       0       0       0       0       0       160     160     160
4(40,3,0)   0   0       0       0       120     120     120     120     160     160     160
5(50,2,0)   0   0       0       0       120     120     120     120     160     220     220

01背包问题，从dp[i-1][j] 到 dp[i][j]多了第i个物品，那么比较一下有买第i个物品和原来不买第i个物品谁更大
如果i是主件，那么可以直接买dp[i][j] = max(dp[i-1][j], v[i] * p[i] + dp[i-1][j-v[i]])
如果i是附件，那么还得先买i的主件dp[i][j] = max(dp[i-1][j], v[q[i]] * p[q[i]] + v[i] * p[i] + dp[i-1][j-v[q[i]]-v[i]])
当然前提是买得起
这样的话前提是把主键放前面，但这个题目每个物品的编号已经定下来了，不行！

分组思路：
附件跳过，只考虑主件
买主件的时候考虑买与其关联的附件的情况
1、只买主件
2、买主件+附件1
3、买主件+附件2
4、买主件+连个附件
f[i][j]=max{
f[i-1][j];//1、不背第i件物品
f[i-1][j-v[i][0]]+p[i][0]*v[i][0];     //2、只背主件 
f[i-1][j-v[i][0]-v[i][1]]+p[i][0]*v[i][0]+p[i][1]*v[i][1] //3、背主件只要附件1 
f[i-1][j-v[i][0]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2]//4、背主件只要附件2 
f[i-1][j-v[i][0]-v[i][1]-v[i][2]]+p[i][0]*v[i][0]+p[i][2]*v[i][2] +p[i][1]*v[i][1];//5、背主件加两个附件


            0   10      20      30      40      50      60      70      80      90      100
0           0   0       0       0       0       0       0       0       0       0       0
1(80,2,0)   0   0       0       0       0       0       0       0       160     160     160
 (40,5,1)   
 (30,5,1)   
2(40,3,0)   0   0       0       0       120     120     120     120     160     160     160
3(50,2,0)   0   0       0       0       120     120     120     120     160     220     220



1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

2200


2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5

7430

 */

public class MainNOIP2006 {
    
    int n;
    int m;
    int[][] v;
    int[][] p;
    
    private MainNOIP2006(int n, int m, int[][] v, int[][] p) {
        super();
        this.n = n;
        this.m = m;
        this.v = v;
        this.p = p;
    }


    

    private int maxProduct() {
        int[][] dp = new int[m+1][n+1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // 什么都不选
                dp[i][j] = dp[i-1][j];
                if (v[i][0] == 0) {
                    continue;
                }
                // 只选主件
                if (j - v[i][0] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], v[i][0] * p[i][0] + dp[i-1][j-v[i][0]]);
                }
                // 选主件+附件1
                if (j - v[i][0] - v[i][1] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], v[i][0] * p[i][0] + v[i][1] * p[i][1] + dp[i-1][j-v[i][0]-v[i][1]]);
                }
                // 选主件+附件2
                if (j - v[i][0] - v[i][2] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], v[i][0] * p[i][0] + v[i][2] * p[i][2] + dp[i-1][j-v[i][0]-v[i][2]]);
                }
                // 选主件+两个附件
                if (j - v[i][0] - v[i][1] - v[i][2] >= 0) {
                    dp[i][j] = Math.max(dp[i][j], v[i][0] * p[i][0] + v[i][1] * p[i][1] + v[i][2] * p[i][2] + dp[i-1][j-v[i][0]-v[i][1]-v[i][2]]);
                }
            }
        }
        /*
        for (int i = 0; i <= m; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        */
        return dp[m][n]*10;
    }


    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt()/10;
        int m = scan.nextInt();
        int[][] v = new int[m+1][3];
        int[][] p = new int[m+1][3];
        for (int i = 1; i <= m; i++) {
            int tempV = scan.nextInt()/10;
            int tempP = scan.nextInt();
            int tempQ = scan.nextInt();
            if (tempQ == 0) {
                v[i][0] = tempV;
                p[i][0] = tempP;
            } else {
                if (v[tempQ][1] == 0) {
                    v[tempQ][1] = tempV;
                    p[tempQ][1] = tempP;
                } else {
                    v[tempQ][2] = tempV;
                    p[tempQ][2] = tempP;
                }
            }
        }
        MainNOIP2006 main = new MainNOIP2006(n, m, v, p);
        System.out.println(main.maxProduct());

    }

}
